/**
 * 数组中第K个大的元素
 * @param nums
 * @param k
 * @returns
 */
const findKthLargest = (nums: number[], k: number): number => {
  let len = nums.length;

  /**
   * 获取左孩子的索引
   * @param i
   * @returns
   */
  const getLeftIndex = (i: number) => (i << 1) + 1;

  /**
   * 获取右孩子的索引
   * @param i
   * @returns
   */
  const getRightIndex = (i: number) => (i << 1) + 2;

  /**
   * 获取左右孩子比较大的索引
   * @param l
   * @param r
   * @returns
   */
  const getMaxI = (l: number, r: number) => {
    if (r >= len) return l; // 右孩子越过的边界
    const lItem = nums[l];
    const rItem = nums[r];
    return lItem > rItem ? l : r;
  };

  /**
   * 交换元素
   * @param l
   * @param r
   * @returns
   */
  const swap = (l: number, r: number) => ([nums[l], nums[r]] = [nums[r], nums[l]]);

  /**
   * 下滤
   * @param i
   */
  const down = (i: number) => {
    const sizes = len >> 1;

    while (i < sizes) {
      // 获取左孩子索引
      const lI = getLeftIndex(i);
      // 获取右孩子索引
      const rI = getRightIndex(i);

      // 获取左右孩子比较大的索引
      const maxI = getMaxI(lI, rI);
      // 当前比孩子还要大, 直接返回
      if (getMaxI(maxI, i) === i) return;

      swap(maxI, i);

      // 更新i
      i = maxI;
    }
  };

  // 原地建堆
  const sizes = (len >> 1) - 1;
  for (let i = sizes; i >= 0; i--) {
    down(i);
  }

  while (k--) {
    swap(0, --len);
    // 对0位置下滤
    down(0);
  }

  return nums[len]
};
